package com.tongtech.proxy.fw;

public class BTSelete<T extends Comparable<T>> {

  private static final boolean RED = true;
  private static final boolean BLACK = false;

  private Node<T> root;

  public void insert(T data) {
      Node<T> newNode = new Node<>(data);
      insert(newNode);
  }

  private void insert(Node<T> newNode) {
      if (root == null) {
          root = newNode;
      } else {
          insertNode(newNode, root);
      }
      newNode.color = RED;
      fixInsert(newNode);
  }

  private void insertNode(Node<T> newNode, Node<T> currentNode) {
      if (newNode.data.compareTo(currentNode.data) < 0) {
          if (currentNode.left == null) {
              currentNode.left = newNode;
              newNode.parent = currentNode;
          } else {
              insertNode(newNode, currentNode.left);
          }
      } else {
          if (currentNode.right == null) {
              currentNode.right = newNode;
              newNode.parent = currentNode;
          } else {
              insertNode(newNode, currentNode.right);
          }
      }
  }

  private void fixInsert(Node<T> newNode) {
      while (newNode != root && newNode.parent.color == RED) {
          if (newNode.parent == newNode.parent.parent.left) {
              Node<T> uncle = newNode.parent.parent.right;
              if (uncle != null && uncle.color == RED) {
                  newNode.parent.color = BLACK;
                  uncle.color = BLACK;
                  newNode.parent.parent.color = RED;
                  newNode = newNode.parent.parent;
              } else {
                  if (newNode == newNode.parent.right) {
                      newNode = newNode.parent;
                      leftRotate(newNode);
                  }
                  newNode.parent.color = BLACK;
                  newNode.parent.parent.color = RED;
                  rightRotate(newNode.parent.parent);
              }
          } else {
              Node<T> uncle = newNode.parent.parent.left;
              if (uncle != null && uncle.color == RED) {
                  newNode.parent.color = BLACK;
                  uncle.color = BLACK;
                  newNode.parent.parent.color = RED;
                  newNode = newNode.parent.parent;
              } else {
                  if (newNode == newNode.parent.left) {
                      newNode = newNode.parent;
                      rightRotate(newNode);
                  }
                  newNode.parent.color = BLACK;
                  newNode.parent.parent.color = RED;
                  leftRotate(newNode.parent.parent);
              }
          }
      }
      root.color = BLACK;
  }

  private void leftRotate(Node<T> node) {
      Node<T> rightChild = node.right;
      node.right = rightChild.left;
      if (rightChild.left != null) {
          rightChild.left.parent = node;
      }
      rightChild.parent = node.parent;
      if (node.parent == null) {
          root = rightChild;
      } else if (node == node.parent.left) {
          node.parent.left = rightChild;
      } else {
          node.parent.right = rightChild;
      }
      rightChild.left = node;
      node.parent = rightChild;
  }

  private void rightRotate(Node<T> node) {
      Node<T> leftChild = node.left;
      node.left = leftChild.right;
      if (leftChild.right != null) {
          leftChild.right.parent = node;
      }
      leftChild.parent = node.parent;
      if (node.parent == null) {
          root = leftChild;
      } else if (node == node.parent.left) {
          node.parent.left = leftChild;
      } else {
          node.parent.right = leftChild;
      }
      leftChild.right = node;
      node.parent = leftChild;
  }

  public static void main(String[] args) {
      BTSelete<Integer> tree = new BTSelete<>();
      tree.insert(15);
      tree.insert(10);
      tree.insert(20);
      tree.insert(5);
      tree.insert(12);
      tree.insert(10); // 插入重复的元素

      System.out.println("中序遍历：");
      tree.inOrderTraversal();
  }

  private void inOrderTraversal() {
      inOrderTraversal(root);
  }

  private void inOrderTraversal(Node<T> node) {
      if (node != null) {
          inOrderTraversal(node.left);
          System.out.print(node.data + " ");
          inOrderTraversal(node.right);
      }
  }

  private static class Node<T> {
      T data;
      boolean color;
      Node<T> parent;
      Node<T> left;
      Node<T> right;

      public Node(T data) {
          this.data = data;
          this.color = RED;
          this.parent = null;
          this.left = null;
          this.right = null;
      }
  }
}